Communication systems for carrying various payload, such as data, sound, video, etc., are becoming nearly ubiquitous. For example, telecommunication systems, such as the public switched telephone network (PSTN), cellular telephone networks, and personal communication systems (PCS), have been deployed to service a very large percentage of the Earth's population. Additionally, data networks, such as the Internet, wide area networks (WANs), metropolitan area networks (MANs), local area networks (LANs), and wireless local area networks (WLANs), are widely available in most urban areas.
The use of such communication networks has become widespread, resulting in not only a large amount of payload traffic being carried by the communication networks but also a wide variety of payload traffic being carried. For example, voice (whether digital or analog), multimedia, text, and image payload are all regularly carried by communication networks.
The widespread use of such communication networks, however, often results in periods of network congestion. Specifically, if unchecked, payload communication volume over a particular network may reach a critical point wherein the network traffic is unacceptably affected (e.g., delayed, degraded, blocked, etc.), communication sessions or connections are dropped, network nodes are unable to function properly, and the like. The foregoing network traffic critical point is referred to herein as network congestion, such that network congestion as used herein means congestion reaching a critical or predefined level as may be defined by network parameters, one or more pre-selected threshold value, a network protocol, a network operator, network users, etc.
Various schemes for avoiding network congestion have been tried. Network congestion avoidance in such schemes was implemented by dropping communication session packets as network traffic reaches or nears network congestion. Such network congestion avoidance schemes are typically implemented with respect to one or more nodes in the network, such as within routers, switches, gateways, servers, etc.
For example, random early detection (RED) RED operates to prevent network congestion as may be experienced at a particular network node by dropping packets before a networking device's buffer capacity is exhausted. Specifically, a network device operating in accordance with a RED algorithm monitors average queue size and assigns a packet dropping probability (P) to each packet based upon the average queue length. The higher packet dropping probability assigned to a packet, the more likely that particular packet is to be dropped. Accordingly, packets will be statistically dropped in accordance with the level of network traffic as represented by the queue length. Operation of a RED algorithm to assign packet dropping probabilities to packets is illustrated in FIG. 1. As can be seen in FIG. 1, if the queue is almost empty (the average queue length is less than minThr), all incoming packets are accepted (i.e., the packet dropping probability is zero, P=0). However, as the average queue length increases, the probability for dropping an incoming packet also increases. When the queue is full (the average queue length is equal to maxThr), the packet dropping probability will be maximum (i.e., the packet dropping probability is maxP, P=maxP, wherein maxP is typically 1 meaning that the packet will be dropped) and most, if not all, of the incoming packets are dropped. When the average queue length falls between the lower threshold and upper threshold (i.e., minThr<avgQ<maxThr) the packet dropping probability will be assigned as a function of the average queue length and the range established by the thresholds (e.g., P=maxP(avgQ−minThr)/(maxThr−minThr)).
Although providing some level of network congestion avoidance, there are a number of imperfections in the performance of RED. For example, the present inventors have observed that dropping packets based solely on average queue length does not always lead to fair bandwidth sharing. That is, the loss rate encountered by all connections is the same as they are each assigned the same packet dropping probability at any particular time. This implies that as traffic levels approach network congestion, the more buffers a communication session or connection occupies, the more the packets will be dropped from that connection. However, this does not always lead to fair bandwidth sharing among the connections due to the different behavior of various connection protocols, such as transport control protocol (TCP) and user datagram protocol (UDP). TCP is an adaptive protocol and will react to packet loss experienced by a connection by slowing the transmission of packets for that connection. However, UDP is not an adaptive protocol, and thus UDP will not react to packet loss experienced by a connection. Accordingly, as shown in FIGS. 2A and 2B, wherein portions 201 and 202 of the UDP and TCP transmission bandwidth, respectively, are dropped through operation of a RED algorithm, the TCP transmissions will be reduced in response to the packet loss. Accordingly, although dropping the same percentage of packets from each of these connections, reduced TCP transmissions will quickly result due to the adaptive nature of TCP whereas the UDP transmissions will not be reduced. This allows the UDP connection to obtain an unfair share of the network bandwidth.
Moreover, RED applies the technique equally to all communications and thus does not accommodate quality of service (QoS) or other priority communication schemes. That is, RED treats all classes of service the same. Therefore, a high priority connection and a low priority connection will both experience the same packet dropping probability. Such a result is not consistent with implementing a QoS application.
Weighted random early detection (WRED) operates to prevent network congestion as may be experienced by a particular network node by dropping packets similar to RED, but adds weighting in packet dropping decision making to accommodate QoS applications. Specifically, WRED combines the capabilities of a RED algorithm with a priority-based feature to provide for preferential traffic handling of higher priority packets. WRED operates to discard packets associated with lower priority traffic when the network node begins to experience congestion. Although WRED will also discard packets associated with higher priority traffic, such higher priority traffic packets will be discarded at a lower probability (rate), and/or at a point when the network is more congested, than packets of the lower priority packets. Accordingly, WRED provides differentiated performance characteristics for different classes of service.
The foregoing differentiated performance for different classes of service is illustrated in FIG. 3. In FIG. 3, lines 301 and 302 represent the drop probabilities for 2 different classes of service (queues). Specifically, in the embodiment of FIG. 3, line 301 represents the drop probability for lower priority connections (x) and line 302 represents the drop probability for higher priority connections (y). In the illustrated embodiment, for a given average queue length, a higher priority connection will always experience lower drop probability than that of a lower priority connection. Also, packets from a lower priority connection will be dropped at an earlier stage of congestion as “Qx_minTh” is smaller than “Qy_minTh”.
Although WRED provides limited preferential traffic handling for packets associated with higher priority traffic, the present inventors have observed that WRED suffers from the unfair bandwidth sharing problems of RED discussed above. That is, dropping packets based solely on average queue length, although implementing weighting as between different classes of service, continues to result in unfair bandwidth sharing between and within the different classes of service.
Flow random early detection (FRED) operates to prevent network congestion as may be experienced by a particular network node by dropping packets similar to RED, but packet dropping probability is based upon buffer usage associated with a flow (i.e., a connection using TCP or UDP). Specifically, FRED uses per-active-flow accounting to impose a packet loss rate resulting from packet dropping that depends on the flow's buffer usage to improve fairness.
As shown in FIG. 4, FRED introduces the parameters to the packet dropping decision making to establish goals for the minimum (minq) and maximum (maxq) number of packets each flow should be allowed to buffer. FRED maintains a count of buffered packets (qBuf) for each flow that currently has any packets buffered. When qBuf for a particular flow is less than minq, the packet dropping probability is zero (P=0) resulting in no packets of that flow being dropped. Correspondingly, when qBuf for a particular flow is greater than maxq, the packet dropping probability is one (P=1) resulting in all packets of that flow being dropped. However, when qBuf for a particular flow is between minq and maxq, packet dropping probability (P) is assigned to packets of the flow based upon the average queue length, as with RED discussed above.
FRED introduces the global parameter which is an estimate of the average per-flow buffer count (avgqBuf). FRED also introduces a parameter which counts the number of times the flow exceeds maxq (strike). FRED operates to penalizes flows with high strike values using the aforementioned avgqBuf. Specifically, flows with high strike values are not allowed to queue more than avgqBuf packets, thereby preventing those flows from having more packets than the average flow. This allows adaptive flows (e.g., TCP) to send bursts of packets, but prevents non-adaptive flows (e.g., UDP) from consistently monopolizing the buffer space. Accordingly, using these parameters, flows with fewer than avgqBuf packets queued are favored over flows with more.
The foregoing notwithstanding, deficiencies still remain in the use of FRED. For example, if a flow uses more than minq buffers and the average queue size (avgQ) is larger than minThr, FRED will drop packets with probability proportional to the avgQ. Thus, in this region of operation, FRED may demonstrate the same kind of bandwidth unfairness as identified above with respect to RED. FRED will impose the same loss rate on all the flows that have more than minq packets buffered, regardless of how much bandwidth they are using. As with RED discussed above, FRED does not support QoS differentiation.
Moreover, the packet dropping probability of a flow in FRED depends upon the number of packets that flow has buffered. Although this scheme may first appear to be a more fair allocation of bandwidth, the present inventors have discovered that such an allocation of buffers can yield very different fairness properties from a truly fair allocation of bandwidth. Where variable packet sizes are used, the larger the packet size, the more bandwidth that will be used. Likewise, where variable data rates are used (e.g., variable modulation techniques are employed), the slower the data rate the more bandwidth that is needed to transmit the same amount of data. Accordingly, fair allocation of packet buffers does not imply truly fair allocation of bandwidth when the packet size and/or the physical transmit data rate is different.